Many real-world problems, systems, organizations and structures can be described in terms of interrelated modules. For example, a combustion engine could be described in very simple terms as elements of one or more combustion chambers, one or more pistons, a transmission, an ignition source, and a fuel supply. Some of these components are linked to others. The pistons, for instance, are linked to the combustion chambers and the drive train, and the fuel supply and ignition source are linked to the combustion chamber. Linked elements may be thought of as forming “modules.” The pistons, combustion chamber, and ignition source, for example, may be described as a single module. In the analysis of many real-world problems, assembling elements into modules can be beneficial for purposes such as simplification of analysis.
Models are known that represent real-world systems and structures in terms of interrelated modules. A directed graph is one example of a model that does so. Another example is dependency structure matrix (“DSM”) models. A DSM is a matrix representation of a directed graph that can be used to represent systems and structures, including a complex system.
FIG. 1 illustrates a simple DSM. The column and row headings in the matrix (A-G) correspond to elements or nodes. “X” marks inside the matrix cells indicate whether corresponding nodes are related. For example, if there is an arrow from node C to node A in a directed graph indicating a relationship between nodes, then an ‘X’ mark is placed in row A and column C. As an alternative to symbols such “X” marks, numerical values may be used to indicate a degree of dependency. For example, a “9” might represent a strong dependency and a “2” a weak dependency. Diagonal elements have no significance and are normally blacked-out or used to store some element-specific attribute(s).
FIGS. 2(a), 2(b) and 2(c) are useful to further illustrate DSM's and their relations to other models, as well as their relation to real-world structures and organizations. FIG. 2(a) is a schematic of a structure where elements A, B, C and D all have a common interface with element E. In this configuration, element E may be referred to as a “bus.” FIG. 2(b) includes two directed graphs that represent the structure of FIG. 2(a). FIG. 2(c) is a DSM that represents the structure and graphs of FIGS. 2(a) and (b).
Once a DSM has been constructed, it can be analyzed to identify modules, referred to within the DSM as clusters. This is a process referred to as “clustering.” The goal of DSM clustering is to find subsets of DSM elements (i.e., the “clusters”) that are mutually exclusive or minimally interacting. That is, clusters contain most, if not all, of the interactions (i.e., “X” marks) internally and the interactions or links between separate clusters are eliminated or minimized to transform the system into independent, loosely coupled, or nearly independent system modules. One of the significances of clusters can be that all or most of the elements within the cluster are largely limited to interact mainly with other elements in the cluster and likewise are not likely to interact with elements outside of the cluster. Clustering is therefore an important part of the usefulness of DSM's since it “transforms” the initial DSM element population into a simpler “modular” model.
As a simple example of clustering, consider the identical DSM's of FIGS. 3(a) and 3(b). Column and row entries have been re-arranged from an initial alphabetic order to create the shaded clusters. As shown, different clustering metrics will result in different clusterings. FIG. 3(a) is the result of one potential clustering, with the cells representing interrelations between nodes D and E left out of clusters. The DSM of FIG. 3(b) shows a second potential clustering that includes the D-E cells, but that also has some overlap between the clusters. Which of these clustering arrangements is preferred over the other depends on a number of factors related to the particular system or model at hand, among other factors.
While the DSM's of FIGS. 1, 2 and 3 are relatively simple, it will be appreciated that many real-world DSM's can be extremely large and/or complex, and for these complex real-world cases clustering methods can be quite difficult. Consider, for instance, a simple three-dimensional structure such as a tetrahedron or three-dimensional pyramid. This is depicted in FIGS. 4(a) and 4(b) showing four equal clusters, each with dense internal relationships and weaker (or sparser) external relationships. If all the clusters are perfectly equal it is purely a matter of chance how any clustering method would present an answer, with one example illustrated in FIG. 4(c). In this example, cluster DD is the one that is visually disrupted most by being presented last in the sequence. This has the effect of spreading its inter-cluster relationships over a wider spatial area, which is depicted in the macro-scale DSM of FIG. (4c) as being lower density blocks of grey. To an untrained observer this might be thought to be a bus structure where cluster DD is the unique possessor of system wide integrating functions and some semi-random cross-linking occurs in the zone AA-CC.
Several methods are known for clustering real-world problems and structures. Several methods for creating modules of variables are discussed, for example, in “Notes on the Synthesis of Form,” by Alexander, C., 1964, Harvard Press, Boston, Mass. Methods for partitioning DSM's are discussed in “The Design Structure System: A Method for Managing the Design of Complex Systems,” by Steward, D. V., IEEE Transactions on Engineering Management 28 (1981) 77-74. Known methods for organizing modules and for clustering DSM's, however, leave many problems unresolved. Many fail to accurately predict the formation of “good” clustering arrangements for complex systems. Many known clustering methods when applied to complex DSM's have difficulty in extracting relevant information from the data, and then conveying the information to a user. Some methods suffer from an oversimplification of the objective function utilized. Others are susceptible to getting trapped in local optimal solutions. Many methods have difficulty in accurately representing busses and three-dimensional structures.